/**
 * 双端队列(deque)是一种允许我们同时从首部和尾部添加和移除元素的特殊队列。
 */
export default class Deque<T> {
    private _item: any;
    private _count: number; // 队列里元素个数
    private _lowestIndex: number; // 尾部新元素即将使用的下标
    constructor() {
        this._item = {}; // 键名要求是非负整数
        this._count = 0;
        this._lowestIndex = 0; // 队列初始化，尾部新元素即将使用的下标当然是0了
    }
    /**
     * 向双端队列的前端添加元素
     */
    public addFront(element: T) {
        if (this.isEmpty()) { // 当双端队列里的没有元素的时候，向前端添加新元素就是向后端添加元素
            this.addBack(element);
        } else if (this._lowestIndex - this._count === 0) { // 当首部元素的下标是0，需要所有的元素往右移
            for (let i = 0; i < this._count; i ++) {
                this._item[this._lowestIndex - i] = this._item[this._lowestIndex - 1 - i];
            }
            this._item[0] = element;
            this._count ++; // 元素新增
            this._lowestIndex ++; // 所有元素往右移会使“尾部新元素即将使用的下标”加一
        } else { // 当首部元素的下标大于0，只需要在首部元素的前一位添加这个新元素
            this._item[this._lowestIndex - this._count - 1] = element;
            this._count ++; // 元素新增，不影响“尾部新元素即将使用的下标”
        }
    }
    /**
     * 向双端队列的后端添加元素
     */
    public addBack(element: T) {
        this._item[this._lowestIndex] = element;
        this._count ++; // 元素新增
        this._lowestIndex ++; // 新增的元素会使“尾部新元素即将使用的下标”加一
    }
    /**
     * 从双端队列的前端移除元素
     */
    public removeFront(): T {
        if (this.isEmpty()) {
            return undefined;
        }
        const headIndex = this._lowestIndex - this._count; // 首部元素下标
        const result = this._item[headIndex];
        delete this._item[headIndex];
        this._count --; // 元素移除，不影响“尾部新元素即将使用的下标”
        return result;
    }
    /**
     * 从双端队列的后端移除元素
     */
    public removeBack(): T {
        if (this.isEmpty()) {
            return undefined;
        }
        const result = this._item[this._lowestIndex - 1];
        delete this._item[this._lowestIndex - 1];
        this._count --;
        this._lowestIndex --;
        return result;
    }
    /**
     * 查看双端队列头元素
     */
    public peekFront(): T {
        if (this.isEmpty()) {
            return undefined;
        }
        return this._item[this._lowestIndex - this._count]; // 首部元素
    }
    /**
     * 查看双端队列尾元素
     */
    public peekBack(): T {
        if (this.isEmpty()) {
            return undefined;
        }
        return this._item[this._lowestIndex - 1];
    }
    /**
     * 如果队列中不包含任何元素，返回true，否则返回false
     */
    public isEmpty(): boolean {
        return this._count === 0;
    }
    /**
     * 清空双端队列
     */
    public clear() {
        this._item = {};
        this._count = 0;
        this._lowestIndex = 0;
    }
    /**
     * 双端队列的大小
     */
    public size() {
        return this._count;
    }
    /**
     * 双端队列的字符串形式
     */
    public toString(): string {
        if (this.isEmpty()) {
            return '';
        }
        const headIndex = this._lowestIndex - this._count; // 首部元素下标
        let objString: string = `${this._item[headIndex]}`;
        for (let i = 1; i < this._count; i ++) {
            objString = `${objString},${this._item[headIndex + 1]}`;
        }
        return objString;
    }
}
